\documentclass{beamer}
\usepackage[brazil]{babel}
\usepackage[utf8]{inputenc}
%\usepackage[latin1]{inputenc}
\usepackage{url}
\usepackage{beamerthemesplit}

%\usepackage{beamerthemeshadow}
%\usepackage{pgf,pgfarrows,pgfnodes,pgfautomata,pgfheaps,pgfshade}
%\usepackage{amsmath,amssymb}
%\usepackage[latin1]{inputenc}
%\usepackage{colortbl}
%\usepackage[english]{babel}
%\usepackage{amsfonts}
%\usepackage{mathrsfs}
%\usepackage{wrapfig}
%\usepackage[twlrm]{rawfonts} %xfig
%\usepackage{graphics}
%\usepackage{psfig}
\usepackage{subfig} % este é para fazer sub figuras
\usepackage{graphicx}
%\usepackage{times}
%\usepackage[all]{xy}

\title[Tradutores {\it Análise Semântica}]{Análise Semântica {\it Tradutores}}
\author[Gabriel Heleno Gonçalves da Silva and Others] {Universidade de Brasília\\Instituto de Ciências Exatas \\Departamento de Ciência da Computação\\Gabriel Heleno Gonçalves da Silva\\Leonardo Melo\\Igor Rafael de Souza}
\date{Brasília, 9 de Janeiro de 2012}

\begin{document}
\begin{frame}

\begin{columns}

\column {0.2\textwidth}
%\includegraphics[scale=0.5]{Logo_UnB.jpg}

\column {0.4\textwidth}
\begin{center}
\scriptsize {Universidade de Brasília\\Departamento de Ciência da Computação}
\end{center}

\end{columns}

\titlepage
\end{frame}


\section{Introdução}

\frame
{
\frametitle{Introdução - Composição da Análise Semântica}
 \begin{itemize}

 \item<1-> A análise semântica é composta pela análise de escopo e tipo e em muitas abordagens também é constituída pela geração de código.

 \item<1-> Para realizar a análise de tipo o analisador semântico utiliza uma série de verificadores

  \item<1-> Um verificador checa se o tipo de uma construção corresponde exatamente àquilo esperado no contexto

  \item<1-> Na abordagem usada no livro texto adotada para as aulas, a verificação é separada em quatro partes: a verificação estática de tipos, de fluxo de controle, a verificação de unicidade e relacionada aos nomes.
  \end{itemize}
}


\frame{
  \frametitle{Verificação de Tipos e Fluxo de Controle}
  \begin{itemize}
  \item<1-> Um compilador deveria relatar um erro se um operador for aplicado a um operando incompatível

  \item<1-> Ex.: se uma variável do tipo array for atribuída a uma variável do tipo função

  \item<1-> Os enunciados que fazem o fluxo de controle deixar uma construção precisam ter algum local para onde transferir o controle

  \item<1-> Ex.: O break em C faz com que o controle deixe o while for ou switch envolvente mais interno. Um erro ocorre se um tal enunciado envolvente não existir

  \end{itemize}
}


\frame{
  \frametitle{Verificações de Unicidade e Nomes}
  \begin{itemize}
  \item<1-> Existem situações em que os objetos precisam ser declarados uma única vez

  \item<1-> Ex.: Um identificador na linguagem não pode ser declarado duas vezes dentro do mesmo contexto

  \item<1-> Em algumas ocasiões, o mesmo nome precisa figurar duas ou mais vezes

  \item<1-> Em Ada, um laço ou bloco precisa ter um nome que apareça no início e ao final da construção

  \item<1-> O compilador precisa verificar se o mesmo nome é usado em ambos os locais
  \end{itemize}
}


\frame{
  \frametitle{Expressões de Tipos e Tipos Básicos}
  \begin{itemize}
  \item<1-> O tipo de uma construção de linguagem será definido por uma "expressão de tipo". Informalmente, uma expressão de tipo ou é um tipo básico ou é formada através da aplicação de um operador, chamado de um construtor de tipos, a outras expressões de tipo

  \item<1-> Dentre os tipos básicos se encontram os booleanos, caracteres e reais. Um tipo especial de tipo, o tipo erro, irá sinalizar o erro durante a verificação

  \item<1-> O tipo básico vazio, denotando a "ausência de valor" permitirá que os comandos sejam verificados

  \item<1-> Ex.: Depois de realizar uma operação, o analisador compara o tipo gerado pela operação com o tipo esperado pelo retorno a partir do momento que encontra o tipo vazio
  \end{itemize}
}


\frame{
  \frametitle{Construtores de tipos}
  \begin{itemize}
  \item<1-> Um construtor de tipo aplicado a uma expressão de tipo é uma expressão de tipo
  \item<1-> Se T é uma expressão de tipo, então array(I,T) é uma expressão de tipo denotando o tipo array de elementos com tipo T e conjunto de índices I. I é frequentemente um intervalo dos inteiros\\
  \item<1-> Ex.: var A: array[1..10] of integer;\\

Associa a expressão de tipo array (1..10, integer) a A

  \item<1-> Se $T_1$ e $T_2$ são expressões de tipo, o produto cartesiano $T_1$ X $T_2$ é uma expressão de tipo

  \item<1-> Assumimos que X associe à esquerda

  \end{itemize}
}


\frame{
  \frametitle{Construtores de tipo - Registros}
  \begin{itemize}
  \item<1-> A diferença entre um registro e um produto é que os campos num registro têm nomes. Um construtor do tipo registro será aplicado a uma tupla formada a partir dos nomes de campos e dos tipos de campos (tecnicamente, os nomes de campo deveriam ser parte do construtor de tipos, mas é conveniente manter os nomes de campo junto aos seus tipos associados.).
  \item<1-> type linha = record
\

\
                 endereco: integer;
\

\
       	        lexema: array [1..15] of char;

  var tabela: array [1..101] of linha;

  registro((endereco X inteiro) X (lexema X array (1..15, caractere)))
  \end{itemize}
}

\frame{
  \frametitle{Construtores de tipo}
  \begin{itemize}
  \item<1-> Ponteiros \\Se T é uma expressão de tipo, então ponteiro (T) é uma expressão de tipo denotando o tipo "ponteiro para um objeto do tipo T"\\
  \item<1-> Funções \\Matematicamente uma função mapeia elementos de um conjunto, o domínio, em outro conjunto, o contra-domínio. Mapeando o domínio de tipos D em um intervalo de tipos R, o tipo de tal função será denotado pelas expressões de tipo D$\rightarrow$R
  \item<1-> Ex.: A função mod de Pascal possui domínio de tipos caractere X caractere, isto é, um par de inteiros, e contra-domínio de tipo ponteiro inteiro. Por conseguinte dizemos que a função mod possui o tipo:\\ caractere x caractere $\rightarrow$ ponteiro inteiro
  \end{itemize}
}

\frame{
  \frametitle{Verificação estática e dinâmica de tipos}
  \begin{itemize}
  \item<1-> A verificação feita por um compilador é dita estática, enquanto que aquela feita enquanto o programa-alvo roda é denominada dinâmica. Em princípio, qualquer verificação pode ser feita dinamicamente, se o código-alvo carregar o tipo do elemento juntamente com o seu valor
  \item<1-> Um sistema sonoro de tipos elimina a necessidade de verificação dinâmica de tipos em busca de erros de tipo, porque nos permite determinar estaticamente que esses erros não poderão ocorrer quando o programa-alvo rodar
  \item<1-> Uma linguagem é fortemente tipada se seu compilador puder garantir que o programa que o mesmo aceita irá executar sem erros de tipos
  \end{itemize}
}


\frame{
  \frametitle{Verificação estática e dinâmica de tipos}
  \begin{itemize}
  \item<1-> Na prática, algumas verificações só podem ser feitas dinamicamente. Por exemplo, se primeiro declararmos\\
\

\
  tabela: array[0..255] of char;
  i: integer;\\
\

\
 E então computarmos tabela[i], um compilador não poderá em geral garantir que, durante a execução, o valor de i repouse no intervalo de 0 a 255
  \end{itemize}
}

\frame{
  \frametitle{Especificação de um verificador simples de tipos}
  \begin{itemize}
  \item<1-> O tipo de cada identificador precisa ser declarado antes de ser usado
\

\
  \item<1-> O verificador de tipos é um esquema de tradução que sintetiza o tipo de cada expressão a partir do tipo de suas sub-expressões. O verificador de tipos pode tratar arrays, ponteiros e funções
  \end{itemize}
}



\frame{
  \frametitle{Exemplo de uma Gramática para uma Linguagem-Fonte}
  \begin{itemize}
  \item<1-> P $\rightarrow$ D;E
  \item<1-> D $\rightarrow$ D;D $|$ id:T
  \item<1-> T $\rightarrow$ char$|$ integer $|$ array [ num ] of T $|$ ponteiro T
  \item<1-> E $\rightarrow$ literal $|$ num $|$ id $|$ E mod E $|$ E [E] $|$ E ponteiro
\

\
  \item<1->  O programa P consiste em uma sequência de declarações D seguidas de uma única expressão E
  \end{itemize}
}

\frame{
  \frametitle{Programa gerado pela gramática}
  \begin{itemize}
  \item<1-> chave: integer
  \item<1-> chave mod 1999
  \item<1-> A linguagem possui dois tipos básicos, char e integer, um terceiro tipo básico tipo\_erro, é usado para sinalizar erros. Por simplicidade, assumimos que todos os arrays comecem por 1
  \item<1-> Ex.: array [256] of char
  \item<1-> Leva à expressão do tipo array(1..256, caractere) consistindo no construtor array aplicado ao subintervalo 1..256 e ao subtipo caractere
  \end{itemize}
}


\frame{
  \frametitle{Esquema de tradução que salva o tipo do identificador}
  \begin{itemize}
  \item<1-> P $\rightarrow$ D;E
  \item<1-> D $\rightarrow$ D;D
  \item<1-> D $\rightarrow$ id:T              {incluir-tipo(id.entrada, T.tipo)}
  \item<1-> T $\rightarrow$ char              {T.tipo := caractere}
  \item<1-> T $\rightarrow$ integer           {T.tipo := integer}
  \item<1-> T $\rightarrow$ ponteiro T        {T.tipo := ponteiro}
  \item<1-> T $\rightarrow$ array [num] of T1 {T.tipo := array(1..num.val,T1.tipo)}
  \end{itemize}
}

\frame{
  \frametitle{Esquema na TS}
  \begin{itemize}
  \item<1-> No esquema de tradução apresentando a ação associada à produção D $\rightarrow$ id:T guarda, para um identificador, um tipo numa tabela de símbolos
\

\
  \item<1-> A ação incluir\_tipo(id.entrada, T.tipo) é aplicada ao atributo sintetizado entrada, que aponta para a entrada de id na tabela de símbolos, e a uma expressão de tipo representada pelo atributo sintetizado tipo, para um não-terminal T
  \end{itemize}
}

\frame{
  \frametitle{Verificação de Tipos das Expressões}
  \begin{itemize}
  \item<1-> Quando uma expressão é identificada o tipo de seus operandos é procurado e verifica-se os operadores que serão utilizados juntamente com esses operandos
\

\
  \item<1-> Ex.: E $\rightarrow$ id { E. tipo := procurar(id.entrada) }
\

\
  \item<1-> E $\rightarrow$ E1 mod E2 { E.tipo := se E1.tipo = inteiro e E2.tipo = inteiro então inteiro senão tipo\_erro }
  \end{itemize}
}

\frame{
  \frametitle{Verificação de Tipos dos Comandos e Funções}
  \begin{itemize}
  \item<1-> Para que um comando ou função sejam executados corretamente é necessário que as expressões a eles associados se adequem ao tipo esperado
\

\
  \item<1-> Ex.: if E then S1     { S.tipo := se E.tipo = booleano então S1.tipo senão tipo\_erro }
\

\
  \item<1-> E $\rightarrow$ E1(E2)           { E.tipo := se E2.tipo s e E1.tipo s $\rightarrow$ t então t senão tipo\_erro }
  \end{itemize}
}

\frame{
  \frametitle{Equivalência das Expressões de Tipo}
  \begin{itemize}
  \item<1-> As regras de verificação nessa última seção possuem a forma "se duas expressões de tipo fores iguais então retornar um certo tipo senão retornar tipo\_erro
  \item<1-> Duas expressões equivalentes ou são do mesmo tipo básico ou são formadas pela aplicação do mesmo construtor de tipos estruturalmente equivalentes
  \item<1-> Ex.: A expressão do tipo inteiro é equivalente somente a inteiro porque ambas representam o mesmo tipo básico.
  \item<1-> Similarmente, ponteiro de inteiro é equivalente somente a ponteiro de inteiro porque os dois são formados através da aplicação do mesmo construtor ponteiro a tipos equivalentes.
  \end{itemize}
}

\frame{
  \frametitle{Problemas dos Nomes para Expressões de Tipo}
  \begin{itemize}
  \item<1-> Em algumas linguagens podem ser dados nomes aos tipos
  \item<1-> Ex.: typedef em C e type em Pascal
  \item<1-> Mas a utilização de nomes diferentes pode causar confusão na identificação da equivalência
  \item<1-> O problema dos nomes para expressões de tipos pode ser verificado no fragmento do programa em pascal a seguir:
\\
  \item<1-> type link = ponteiro celula;
  \item<1-> var proximo : link;
  \item<1->     anterior : link;
  \item<1->     p : ponteiro celula;
  \item<1->     q, r : ponteiro celula;

  \end{itemize}
}

\frame{
  \frametitle{Problemas dos Nomes para Expressões de Tipo}
  \begin{itemize}
  \item<1-> Se for utilizada a equivalência por nome, as variáveis são de tipos diferentes, pois o tipo link é de nome diferente do tipo ponteiro celula
\

\
  \item<1-> Entretanto se for utilizada a equivalência estrutural as variáveis serão consideradas como se fossem equivalentes
  \end{itemize}
}


\frame{
  \frametitle{Ciclos na Representação de Tipos}
  \begin{itemize}
  \item<1-> Se considerarmos uma lista ligada de celula, cada uma contendo uma informação do tipo inteiro e um ponteiro para o próximo elemento
  \item<1-> type link = ponteiro celula
  \item<1-> celula = record
  \item<1->      info : integer
  \item<1->      proximo : link;
  \item<1-> end;
  \item<1-> Poderemos ter um ciclo na representação de tipos já que link é um ponteiro para celula e celula é um registro que contém um link
  \item<1-> Para evitar esse tipo de problema sugere-se a construção de registros da mesma forma que é feita em C
  \end{itemize}
}


\frame{
  \frametitle{Ciclos na Representação de Tipos}
  \begin{itemize}
  \item<1-> Representação acíclica de estrutura em C com uso de ponteiro
\

\
  \item<1-> struct celula\{
  \item<1->     int info;
  \item<1->     struct celula *proximo;
  \item<1-> \};
  \end{itemize}
}


\frame{
  \frametitle{Conversões de tipos}
  \begin{itemize}
  \item<1-> A definição da linguagem especifica quais as conversões que são necessárias. 
  \item<1-> Ex.: x + i, sendo que x é inteiro e i é real. Diferentes instruções de máquina são usadas para as operações sobre inteiros e reais. O compilador pode ter que primeiro converter um dos operandos de + para assegurar que ambos os operandos sejam do mesmo tipo quando a adição tiver lugar. 
  \item<1-> Quando um inteiro é atribuído a um real ou vice-versa, a conversão deve ser feita para o tipo do lado esquerdo da atribuição.
  \item<1-> char $\leftarrow$ int $\leftarrow$ long $\leftarrow$ float $\leftarrow$ double, onde os que estão à esquerda serão convertidos nos que estão à direita, dependendo da operação.  
  \end{itemize}
}

\frame{
  \frametitle{Conversões de tipos}
  \begin{itemize}
  \item<1-> Nas expressões, a transformação usual converte um inteiro para um real e, em seguida, realiza a operação no par resultante de operandos reais.
  \item<1-> Exemplo: x i {\bf inttoreal} +. Aqui o operador x i {\bf inttoreal} + converte i de inteiro para real e em seguida é realizada a adição real de seus operandos.
  \item<1-> Um símbolo que tenha diferentes significados dependendo do seu contexto é dito sobrecarregado.
  \end{itemize}
}

\frame{
  \frametitle{Coerções}
  \begin{itemize}
  \item<1-> Implícita: feita automaticamente pelo compilador.
  \item<1-> Explícita: caso o programador precise escrever alguma coisa para provocar a conversão. 
  \item<1-> Ex.: b = (int)a sendo que a é short.
  \item<1-> As conversões implícitas estão limitadas em muitas linguagens às situações onde nenhuma informação é perdida em princípio.
  \item<1-> Ex.: inteiro para real, mas não real para inteiro.
  \end{itemize}
}

%\frame{
%  \frametitle{Produção}
%  \begin{itemize}
%  \item<1-> E $\rightarrow$ {\bf num}
%  \item<1-> E $\rightarrow$ {\bf num}.{\bf num}
%  \item<1-> E $\rightarrow$ {\bf id}
%  \item<1-> E $\rightarrow$ E1 {\bf op} E2
%  \end{itemize}
%}

\frame{
  \frametitle{Regra Semântica}
\begin{tabbing}
  E.tipo := inteiro \\ 
  E.tipo := real \\
  E.tipo := procurar({\bf id}.entrada) \\
  E.tipo \= := \\ 
  \> {\bf se} E1.tipo = inteiro {\bf e} E2.tipo = inteiro {\bf então} inteiro \\
  \> {\bf senão} {\bf se} E1.tipo = inteiro {\bf e} E2.tipo = real {\bf então} real \\
  \> {\bf senão} {\bf se} E1.tipo = real {\bf e} E2.tipo = inteiro {\bf então} real \\
  \> {\bf senão} {\bf se} E1.tipo = real {\bf e} E2.tipo = real {\bf então} real \\
  \> {\bf senão} tipo\underline{ }erro
\end{tabbing}
}

\frame{
  \frametitle{Sobrecarga}
  \begin{itemize}
  \item<1-> Símbolo sobrecarregado é aquele que possui diferentes significados dependendo de seu contexto. 
  \item<1-> Ex.: a = b/c // divisão é inteira ou real?
  \item<1-> Os operadores aritméticos são sobrecarregados na maioria das linguagens. 
  \item<1-> A sobrecarga envolvendo operadores como + pode ser resolvida olhando-se somente para os argumentos do operador. 
  \item<1-> Ex.: a + b = c, onde "a" é inteiro e "b" float, logo "c" será float.
  \item<1-> A sobrecarga é resolvida quando um único significado para uma ocorrência de um símbolo sobrecarregado é determinado.
  
  \end{itemize}
}

\frame{
  \frametitle{Funções Polimórficas}
  \begin{itemize}
  \item<1-> Cada vez que um procedimento polimórfico é chamado, os enunciados em seu corpo podem ser executados com argumentos de diferentes tipos.
  \item<1-> O termo "polimórfico" pode também ser aplicado a qualquer trecho de código que possa ser executado com argumentos de tipos diferentes e dessa forma podemos falar igualmente de funções e de operadores polimórficos.
  \item<1-> Operadores embutidos para indexar arrays, aplicar funções e manipular apontadores são usualmente polimórficos, porque não estão restritos a um tipo particular de array, função ou apontador.
  \end{itemize}
}

\frame{
  \frametitle{Funções Polimórficas}
  \begin{itemize}
  \item<1-> Ex.: O operador \& em C é polimórfico, pois "se o tipo do operandor for '...', o tipo do resultado é um apontador para '...'". Uma vez que qualquer tipo pode ser substituído no lugar de '...', podemos concluir que \& em C é polimórfico.
  \item<1-> São atraentes porque facilitam a implementação de algoritmos que manipulam estruturas de dados, independetemente dos tipos de seus elementos.
  \item<1-> Ex.: Um programa que determine o comprimento de uma lista sem termos que saber os tipos dos elementos da mesma. 
  \item<1-> comprimento (["sol", "lua", "ter"]);
  \item<1-> comprimento ([1,2,3]);
  \end{itemize}
}

\frame{
  \frametitle{Funções Polimórficas}
  \begin{itemize}
  \item<1-> Em pascal são necessárias as especificações completas dos tipos dos parâmetros de funções.
  \item<1-> Uma função C ou Pascal, por exemplo, exige que os tipos dos parâmetros sejam especificados na definição da função, não sendo possível definir uma função verdadeiramente polimórfica.
  \end{itemize}
}

\frame{
  \frametitle{Variáveis de tipo}
  \begin{itemize}
  \item<1-> Uma aplicação importante é a de verificar o uso consistente dos identificadores numa linguagem que não requeira que os identificadores sejam declarados antes de serem usados.
  \item<1-> Obs: C requer declaração dos identificadores antes de serem usados.
  \item<1-> Em algumas linguagens, verifica-se se o identificador não declarado é usado mais como, por exemplo, inteiro ou array. Caso a variável sempre for usada como um inteiro, então não somente asseguramos o uso consistente como, no processo, inferimos o que seu tipo tem que ser.
  \end{itemize}
}

\frame{
  \frametitle{Variáveis de tipo}
  \begin{itemize}
  \item<1-> Inferência de tipos é o problema de determinar o tipo de uma construção de linguagem a partir da forma que for usada.
  \item<1-> Podem ser aplicadas a programas em linguagens pascal e C para preencher as informações de tipos ausentes em tempo de compilação.
  \item<1-> Ex.: 

	\begin{tabbing}
		type link $\uparrow$ celula; \\
		procedure mlist (lptr : link; procedure p); \\
		begin \= \\
		\> while \= lptr != nil do begin \\
		\> \> p (lptr); \\
		\> \> lptr := lptr $\uparrow$.proximo \\
		\> end \\
		end;
	\end{tabbing}

  \end{itemize}
}

\end{document}
